#ifndef __DOUBLELINKLIST_H_
#define __DOUBLELINKLIST_H_

#include <iostream>
#include <stddef.h>
template <typename T>
class doubleLinkList{
    public:
        doubleLinkList();
        ~doubleLinkList();
        void insertTail(const T& element);
        void removeByIndex(size_t index);
        T&   findByIndex(size_t index);
        size_t Size(){return size;};
        template<typename U>
        friend std::ostream& operator<<(std::ostream&os,const doubleLinkList<U>& list);
    private:
    struct Node{
        Node(const T& element){
            data=element;
            next=prev=nullptr;
        }
        T data;
        Node *next;
        Node *prev;
    };
    Node *head;
    Node *tail;
    size_t size;
};

template<typename T>
std::ostream& operator<<(std::ostream&os,const doubleLinkList<T>&list){
    //告诉编译器后面跟的是一个数据类型
    typename doubleLinkList<T>::Node *travelPoint=list.head->next;
    while(travelPoint!=nullptr){
        std::cout<<travelPoint->data<<" ";
        travelPoint=travelPoint->next;
    }
    std::cout<<std::endl;
    return os;
}


template <typename T>
doubleLinkList<T>::doubleLinkList(){
    head=tail=new Node(T()); //匿名对象T()
}


template <typename T>
doubleLinkList<T>::~doubleLinkList(){
    while(head!=nullptr){
        Node *nextNode=head->next;
        delete head;
        head=nextNode;
    }
    tail=nullptr;
    size=0;
}

template <typename T>
inline void doubleLinkList<T>::insertTail(const T& element)
{
    Node *newNode = new Node(element);
    tail->next=newNode;
    newNode->prev=tail;
    tail=newNode;
    size++;
}

template <typename T>
void doubleLinkList<T>::removeByIndex(size_t index){
    if(index>=size){
        std::cout<<"删除位置非法\n";
        return;
    }
    typename doubleLinkList<T>:: Node *travelPoint=head;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    doubleLinkList<T>::Node *freeNode =travelPoint->next;
    travelPoint->next=freeNode->next;
    if(freeNode->next!=nullptr)
        freeNode->next->prev=travelPoint;
    else{
        tail=travelPoint;
    }
    delete freeNode;
    size--;
}

template <typename T>
T&  doubleLinkList<T>::findByIndex(size_t index){
   typename doubleLinkList<T>:: Node* travelPoint =head->next;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    return travelPoint->data;
}

#endif